目標：
這題主要目的在於進一步講解需要二維陣列輔助解的DP問題。

原題：

Question:
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.

Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:
Input: m = 7, n = 3
Output: 28

分析/解題：
有一個m x n大小的格子，其左上處有一台機器人，
每次機器人僅能選擇往右或往下走，目的是要達到右下角的Finish的位置，
題目問說當給定m和n時，有多少種不同的方法可以從左上走到右下？

這題也是典型的動態規劃題目，只要稍稍思考一下，
我們就能發現一件事情：
走到任何一個點的方式，取決於走到其左的方法數加上走到其上的方法數。

那麼，再思考一下走到左邊跟走到上面會有重複的狀況嗎？顯然是不會的。
因為走到一個格子的左邊，
顯然和走到其上面會相差往下走一格及往右走一格的動作，
而且因為機器人也只能往下或往右，所以沒辦法再回頭，
故已經走過的部分不可能再繞得回來。

在這個狀況的特例有幾個：

1. 機器人所站的原點 (按我們的定義一開始就在此，故可以將方法數定為1)
2. 最左邊的一排格子 (僅取決於走到其上面格子的方法數)
3. 最上面的一排格子 (僅取決於走到其左邊格子的方法數)

而實際上從第1點來推算的話，
我們可以知道最左邊一排跟最上面到達的方法數都會是1。
所以我們可以先將這三點的部分先設定為1，
接著從較小的index開始沿途把到達每個點的方法算出來，
直到最後將整個grid算完。

在這個方法下，我們需要一個m x n的陣列用以儲存方法數，
為了方便起見，我們就直接叫它dp，讀者亦可命名為grid，
請留意這些命名都只是方便起見，只要你的命名能和面試官溝通即可，
我們現在並不是在寫一個大的project，
簡短命名並告知你的面試官你的目的是筆者推薦的做法。

計算完畢後，最後僅需回傳dp[m-1][n-1]即可。
(註:由於這邊row跟column的交換並不影響結果，
故我們這邊不特別去在意m和n的前後順序。)

Java:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

Python這邊收尾的時候可以用dp[-1][-1]來表示尾端的元素，
宣告的時候則採用list comprehension(列表解析式/列表表達式)。

Python:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(均為O(m * n))

「空間複雜度是否可以降低？」
(理論上可以，因為實際每次處理的關連部分僅有兩行或兩列，
反覆利用應該可以讓空間需求降低到O(m)或O(n)，但時間複雜度一致)

「是否有更簡單的解？」
(DP的話，沒有，數學的話，有。
假設往下叫D，往右叫R，求不同走法的過程，
即相當於在求(n-1)個D和(m-1)個R的不同排列方法，
故答案會是(m-1+n-1)!/(m-1)!(n-1)!，
此時空間複雜度為O(1)，時間複雜度為O(m+n)。
但階乘的部分當值過大時有可能會有超過int的可能性。)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0169. Majority Element (Easy)